The present disclosure relates to data encoding.
During the encoding of data to be stored using erasure codes, the computing system computing the parities associated with the encoded data can introduce errors that finally propagate to the storage medium and lie there undetected. Common errors that can typically be introduced into the data include system bus errors, internal bus errors, cache bit flip errors, and in-memory bit flips errors, although other errors are occur.
The errors that can arise in computer storage systems pose a threat to data durability and integrity because they can occur undetected, and as a result, produce data that is different from the original data to be stored.
Some existing systems can detect the above-described errors by erasure encoding the data over low order Galois fields, such as a 2-Galois Field (GF (2)), and applying cyclic redundancy check (CRC) operations on the erasure encoded data to verify that the data being stored is valid. More particularly, these existing systems use CRC algorithms that exploit the linearity property over low order Galois fields to detect errors (e.g., use coefficients equal to 1). This linearity property can be used to predict the CRC of the generated parities from the CRC of the input data using bitwise operations.
However, given the electronic and digital device technology, the amount of data that is being processed and stored is rapidly increasing, and so is the number of errors and the amount of processing that is required to verify the integrity of that data. The approaches used by these existing systems are not scalable at the same rate, and can lead to processing bottlenecks and high computing resource costs.
Even more, just using higher order Galois fields such as 256-Galois Field (GF (256)) in the place of a lower order Galois fields (e.g., (GF (2))) for the encoding and CRC generation process is inadequate to address the scaling issue because such higher order CRC functions, by themselves, do not exhibit the linearity property described above for CRCs over low order Galois fields, and as a result, are not amenable to bitwise operations (e.g., like XOR).